﻿using System;

namespace Msngr
{
    public class LinkedList<T> where T : IComparable
    {
        private Node root;
        private int length;

        public int Length { get { return length; } }

        public class Node
        {
            public T data;
            public Node next;

            public Node(T data)
            {
                this.data = data;
            }
        }

        public void AddAtBeggining(T data)
        {
            Node node = new Node(data);
            node.next = root;
            root = node;
            length++;
        }
        
        //Optimize
        public void AddAtEnd(T data)
        {
            Node node = new Node(data);
            if (root == null) 
            {
                root = node;
                return; 
            }
            Node cNode = root;
            while (cNode.next != null) cNode = cNode.next;
            cNode.next = node;
            length++;
        }

        public bool Remove(T data)
        {
            Node cNode = root;
            Node prev = null;
            while (cNode != null)
            {
                if (cNode.data.Equals(data))
                {
                    if (prev != null) prev.next = cNode.next;
                    else root = root.next;
                    length--;
                    return true;
                }
                prev = cNode;
                cNode = cNode.next;
            }
            return false;
        }

        //Verify
        public bool RemoveAtIndex(int index)
        {
            if (index > length) return false;
            if (index == 0) 
            {
                root = root.next;
                return true;
            }
            Node cNode = root;
            Node prev = null;
            for(int i = 0; i <= index - 1; i++)
            {
                    prev = cNode;
                    cNode = cNode.next;
            }
            prev.next = cNode.next;
            return false;
        }

        public Node GetNodeAtIndex(int index)
        {
            if (index > length) return null;
            Node cNode = root;
            for (int i = 0; i <= index - 1; i++) cNode = cNode.next;
            return cNode;
        }

        public int GetIndexOf(T data)
        {
            Node cNode = root;
            int index = 0;
            while (cNode.next != null)
            {
                if (cNode.data.Equals(data)) return index;
                index++;
                cNode = cNode.next;
            }
            return -1;
        }

        public bool HasValue(T data)
        {
            Node cNode = root;
            while (cNode.next != null)
            {
                if (cNode.data.Equals(data)) return true;
                cNode = cNode.next;
            }
            return false;
        }

        public void Sort()
        {
            root = QuicTSort(this).root;
        }

        private LinkedList<T> QuicTSort(LinkedList<T> list)
        {
            if (list.length <= 1) return list;
            LinkedList<T> left = new LinkedList<T>();
            LinkedList<T> right = new LinkedList<T>();
            Node pivot = list.GetNodeAtIndex((int)list.length / 2);
            list.Remove(pivot.data);
            Node cNode = list.root;
            while (cNode != null)
            {
                if (pivot.data.CompareTo(cNode.data) >= 0) left.AddAtEnd(cNode.data);
                else right.AddAtEnd(cNode.data);
                cNode = cNode.next;
            }
            return Glue(QuicTSort(left), new Node(pivot.data), QuicTSort(right));
        }

        private LinkedList<T> Glue(LinkedList<T> left, Node center, LinkedList<T> right)
        {
            Node cNode;
            LinkedList<T> list = new LinkedList<T>();
            cNode = left.root;
            while (cNode != null)
            {
                list.AddAtEnd(cNode.data);
                cNode = cNode.next;
            }
            list.AddAtEnd(center.data);
            cNode = right.root;
            while (cNode != null)
            {
                list.AddAtEnd(cNode.data);
                cNode = cNode.next;
            }
            return list;
        }

        public void ClearList()
        {
            root = null;
        }

        public override string ToString()
        {
            Node cNode = root;
            String list = String.Empty;
            while (cNode != null)
            {
                list += cNode.data.ToString() + ",";
                cNode = cNode.next;
            }
            return list.Substring(0, list.Length - 1);
        }
    }
}